package developer.笔试题.最小差;

/**
 * @author zhangyongkang
 * @time 2025/8/14 11:50
 * @description 有一个包含N个整数的数组，请编写一个算法
 * ，找到其中的两个元素，使它们之差最小。时间复杂度必须为O(n)。
 */
public class MinCha {


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.min(new int[]{3, 1, 4, 6}));
    }

    public static class Solution {
        public int min(int[] nums) {
            buildMaxHeap(nums);//构建大根堆
            Integer pre = null;
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                int num = nums[0];
                swap(nums, 0, nums.length - i - 1);
                modifyHeap(0, nums.length - i - 1, nums);
                if (pre == null) {
                    pre = num;
                    continue;
                } else {
                    min = Math.min(min, pre - num);
                    pre = num;
                }
            }
            return min;
        }

        private void buildMaxHeap(int[] nums) {
            //从下往上构建
            int loopSize = nums.length / 2 - 1;
            for (int i = loopSize; i >= 0; i--) {
                modifyHeap(i, nums.length, nums);
            }
        }

        private void modifyHeap(int maxIdx, int limit, int[] nums) {
            int currentMaxIdx = maxIdx;
            int leftIdx = maxIdx * 2 + 1;
            int rightIdx = maxIdx * 2 + 2;

            if (leftIdx < limit && nums[leftIdx] > nums[currentMaxIdx]) {
                currentMaxIdx = leftIdx;
            }
            if (rightIdx < limit && nums[rightIdx] > nums[currentMaxIdx]) {
                currentMaxIdx = rightIdx;
            }

            if (currentMaxIdx != maxIdx) {
                //进行交换
                swap(nums, currentMaxIdx, maxIdx);
                modifyHeap(currentMaxIdx, limit, nums);
            }
        }

        private void swap(int[] nums, int a, int b) {
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }

}
